<?php


class Node
{
    public $value;
    public $child_left;
    public $child_right;
}

//      1
//   2      3
// 4   5  6   7
function tree($head)
{
    if (!$head) {
        return;
    }

    echo $head->value, PHP_EOL;
    tree($head->child_left);

//    echo $head->value,PHP_EOL;
    tree($head->child_right);
//    echo $head->value,PHP_EOL;
}

function tree_1($head)
{
    $stack = [];
    array_push($stack,$head) ;
    while (!empty($stack)) {

        $node = array_pop($stack);

        echo $node->value, PHP_EOL;
        if ($node->child_right != null) {
            $stack[] = $node->child_right;
        }
        if ($node->child_left != null) {
            $stack[] = $node->child_left;
        }

    }

}


function tree_end($head)
{
    $stack = [];
    $help = [];
    $stack[] = $head;
    while (!empty($stack)) {
        $node = array_pop($stack);
        $help[] = $node;

        if ($node->child_left != null) {
            $stack[] = $node->child_left;
        }

        if ($node->child_right != null) {
            $stack[] = $node->child_right;
        }

    }


    while (!empty($help)) {
        $node = array_pop($help);
        echo $node->value, PHP_EOL;
    }

}

function tree_in($node)
{
    $stack = [];
    while (!empty($stack) || !empty($node)) {
        if (!empty($node)) {
            $stack[] = $node;
            $node = $node->child_left;
        } else {
            $node = array_pop($stack);
            echo $node->value, PHP_EOL;
            $node = $node->child_right;
        }
    }
}


$a = new Node();
$b = new Node();
$c = new Node();
$d = new Node();
$e = new Node();
$f = new Node();
$g = new Node();
$h = new Node();
$i = new Node();

$a->value = '1';

$b->value = '2';
$c->value = '3';

$d->value = '4';
$e->value = '5';

$f->value = '6';
$g->value = '7';

//   1
//  2  3
$a->child_left = $b;
$a->child_right = $c;

//   2
// 4  5

$b->child_left = $d;
$b->child_right = $e;


//   3
//  6   7

$c->child_left = $f;
$c->child_right = $g;


//tree($a);
//tree_1($a);


//tree_in($a);


tree_end($a);

